package demo1;
import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;

/**
 * 单词拆分
 * 时间复杂度O（n） -->查询时间复杂度为O（1），故不加计算
 * 空间复杂度O（n）*/
public class DynamicPlanningPractise {
    List<Integer> list = new ArrayList<>();
    public boolean wordBreak(String s, List<String> wordDict) {
        /**
         状态表示：
         dp[i]表示[0,i]区间内的字符串是否能被字典中的单词拼接而成
         状态转移方程：
         dp[i] = dp[j-1]&&s.subString(j,i+1) contains wordDict
         初始化：
         dp[0] = true;
         返回值：
         dp[n] */
        int n = s.length();
        //1 创建dp表
        boolean[] dp = new boolean[n+1];
        //2 初始化
        s = " "+s;
        dp[0] = true;
        //3 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= i; j++) {
                if(dp[j-1] && (wordDict.contains(s.substring(j,i+1)))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }

    /**
     * 环绕字符串中唯一的子字符串
     * 时间复杂度O（n）
     * 空间复杂度O（n）*/
    public int findSubstringInWraproundString(String s) {
        /**
         状态表示：
         由经验+题目要求可得
         dp[i] 代表以i位置为结尾时，所有子字符串中出现在base中的字符串的个数
         状态转移方程：
         可以将以i位置结尾的所有子字符串分为两种：
         一是 长度为1的字符串
         二是 长度大于1的字符串
         由于s由所有小写字母组成，而base包含了所有小写字母，故情况一必定为1
         情况二中，当s.charAt(i)-1==s.charAt(i-1) || s.charAt(i)=='a' && s.charAt(i-1)=='b'时，
         dp[i] = dp[i-1],即是i位置的字符可以和i-1位置的字符相连时
         初始化：
         由于s中的每个字符都存在与base中，故其必定存在1，所以我将其全部初始化为1，那么状态转移方程也要随之更改
         返回值：
         将同字符结尾的最长dp值存入对应数组，返回数组和*/
        char[] chars = s.toCharArray();
        int n = chars.length;
        //1 创建dp表
        int[] dp = new int[n];
        //2 初始化
        Arrays.fill(dp,1);
        //3 填表
          /**
           * 因为初始化采用的全局初始化，dp表中的所有元素均为1，故无需讨论第一种情况
           * 当当前字符与前字符可连接时，dp[i]+=dp[i-1]即可*/
        for(int i = 1; i < n; i++)
            dp[i] += chars[i]-1==chars[i-1] || chars[i]=='a' && chars[i-1]=='z' ? dp[i-1] : 0;
        //4 返回值
          /**
           此时dp表中存储的是未经去重的子字符串个数，为了体现唯一性，需要对其去重
           去重的思想是：
            将以相同字符为结尾的子字符串，仅取其长度最长的（短的所有可能均被长的所包含）* */
        int[] ret = new int[26];
        for(int i = 0; i < n; i++)
            if(dp[i]>ret[chars[i]-'a'])
                ret[chars[i]-'a'] = dp[i];
        int sum = 0;
        for(int x : ret)
            sum+=x;
        return sum;
    }

}
